package com.sukaiyi.leetcode._45jump_game_ii;

import org.junit.jupiter.params.ParameterizedTest;
import org.junit.jupiter.params.provider.Arguments;
import org.junit.jupiter.params.provider.MethodSource;

import java.io.IOException;
import java.io.InputStream;
import java.util.*;
import java.util.stream.Stream;

import static org.junit.jupiter.api.Assertions.assertEquals;

/**
 * @author sukaiyi
 * @date 2020/05/06
 * @see <a href="https://leetcode-cn.com/problems/jump-game-ii">题目地址</a>
 */
public class Solution {

    @ParameterizedTest
    @MethodSource("commonParamGenerator")
    public void test(int expected, int[] data) {
        assertEquals(expected, jump(data));
    }

    @ParameterizedTest
    @MethodSource("largeParamGenerator")
    public void largeTest(int expected, int[] data) {
        assertEquals(expected, jump(data));
    }

    @ParameterizedTest
    @MethodSource("commonParamGenerator")
    public void testGraph(int expected, int[] data) {
        assertEquals(expected, jumpGraph(data));
    }

    @ParameterizedTest
    @MethodSource("largeParamGenerator")
    public void largeGraphTest(int expected, int[] data) {
        assertEquals(expected, jumpGraph(data));
    }

    static Stream<Arguments> commonParamGenerator() {
        return Stream.of(
                Arguments.of(0, new int[]{0}),
                Arguments.of(2, new int[]{2, 3, 1, 1, 4}),
                Arguments.of(2, new int[]{2, 3, 0, 1, 4}),
                Arguments.of(3, new int[]{5, 9, 3, 2, 1, 0, 2, 3, 3, 1, 0, 0})
        );
    }

    static Stream<Arguments> largeParamGenerator() throws IOException {
        try (InputStream is = Solution.class.getResourceAsStream("largecase.txt")) {
            int available = is.available();
            byte[] buff = new byte[available];
            int len = is.read(buff, 0, available);
            String content = new String(buff);
            int[] largeCase = Arrays.stream(content.split(",")).mapToInt(Integer::parseInt).toArray();
            return Stream.of(
                    Arguments.of(2, largeCase)
            );
        }
    }

    public int jumpGraph(int[] nums) {
        if (nums.length == 1) {
            return 0;
        }
        int start = 0;
        int end = 0;
        int step = 0;
        while (true) {
            step++;
            int next = 0;
            for (int i = start; i <= end; i++) {
                next = Math.max(i + nums[i], next);
            }
            if (next >= nums.length - 1) {
                return step;
            }
            start = end + 1;
            end = next;
        }
    }


    public Integer jump(int[] nums) {
        if (nums.length == 1) {
            return 0;
        }
        Integer[] dp = new Integer[nums.length];
        dp[nums.length - 1] = 0;
        dp[nums.length - 2] = nums[nums.length - 2] == 0 ? null : 1;
        for (int i = nums.length - 2; i >= 0; i--) {
            int steps = nums[i];
            for (int j = 1; j <= steps && i + j < nums.length; j++) {
                if (dp[i + j] == null) {
                    continue;
                }
                if (dp[i] == null) {
                    dp[i] = dp[i + j] + 1;
                } else {
                    dp[i] = Math.min(dp[i], dp[i + j] + 1);
                }
            }
        }
        return dp[0];
    }
}
